<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>Document</title>
    </head>
    <body>
        <script>
            /* 
            返回两个数组中最长的公共子数组
            ①贪心，双重for循环，确定相同的元素，然后再用一个for循环，判断接下来的元素是否相同
            ②dp
             dp[i][j]表示长度为i,下标为(0,i-1)的nums1和长度为j的nums2构成的最长公共子数组
            ②状态转移方程
              如果nums[i-1]==nums[j-1]
              dp[i][j]=dp[i-1][j-1]+1
            
            */
            var findLength = function (nums1, nums2) {
                let result = 0
                let dp = new Array(nums1.length + 1).fill().map(() => new Array(nums2.length + 1).fill(0))
                for (let i = 1; i <= nums1.length; i++) {
                    for (let j = 1; j <= nums2.length; j++) {
                        if (nums1[i - 1] == nums2[j - 1]) {
                            dp[i][j] = dp[i - 1][j - 1] + 1
                            result = Math.max(result, dp[i][j])
                        }
                    }
                }
                return result
                //注意，dp[i][j]表示的是以nums[i-1]和nums[j-1]结尾，但并不一定它结尾就是最大的，所以每次都需要比较最大值
                //我之前的那种写法 return Math.max(...dp[nums1.length])就是默认以nums1最后一个结尾它就是最大的了，但实际不一定
                //比如[1,0,0,0] [1,0,1,1]
            }
            console.log(findLength([1, 2, 3, 2, 1], [3, 2, 1, 4, 7]))
        </script>
    </body>
</html>
